package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: RadixSort
 * @Description: 基数排序（桶排序扩展）
 * @Auther: tanggy3
 * @Date: 10:29 2022/8/30
 * @version : V1.0
 */
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, -542, 748, -14, 214};
        int arr1[] = {8, 4, 5, -7, 1, 3, 6, 2 };
        System.out.println(Arrays.toString(radixSortF(arr)));

        //radixSort(Utils.getIntArr(8000000));//八千万堆溢出
    }


    /**
     * 基数排序（分位数排序）
     * @param arr
     * @return
     */
    static int[] radixSort(int arr[]) {
        long l = System.currentTimeMillis();
        //计算出最大的位数是几位数，就要几次大循环
        int count = maxCount(arr);
        /**
         * 定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
         * 1. 二维数组包含10个一维数组
         * 2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
         * 3. 明确，基数排序是使用空间换时间的经典算法
         */
        int[][] bucket = new int[10][arr.length];
        //记录每一个桶中存放的数据数量
        int[] bucketCountArr = new int[10];
        for (int i = 0; i < count; i++) {
            //遍历原始数组
            for (int j = 0; j < arr.length; j++) {
                //处理个位数，按照第一次进来,%取余
                int v = arr[j] / (int) (Math.pow(10, i)) % 10;
                //放进对应的桶里，且记录好在桶里的位置
                bucket[v][bucketCountArr[v]] = arr[j];
                //放了数字以后桶中的元素个数需要加一
                bucketCountArr[v]++;
            }

            //辅助变量，帮忙把桶中的元素全部复制到原始数组中
            int index = 0;
            //遍历桶数据量数组，不为0的就需要遍历其值，从桶中拿出对应的数放回原始数组
            for (int k = 0; k < bucketCountArr.length; k++) {
                if (bucketCountArr[k] != 0) {
                    for (int m = 0; m < bucketCountArr[k]; m++) {
                        //k，代表k号桶，m代表桶中的第m个元素
                        arr[index++] = bucket[k][m];
                    }
                    //记得把桶数量计数器清零
                    bucketCountArr[k] = 0;
                }
            }
            System.out.printf("第%d次排序结果" + Arrays.toString(arr), i + 1);
            System.out.println("");
        }
        System.out.println("耗时" + (System.currentTimeMillis() - l) + "ms");
        return arr;
    }

    static int[] radixSortStep(int arr[]) {

        /**
         * 定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
         * 1. 二维数组包含10个一维数组
         * 2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
         * 3. 明确，基数排序是使用空间换时间的经典算法
         */

        int[][] bucket = new int[10][arr.length];
        //桶中存放个数
        int[] bucketCountArr = new int[10];

        //第1轮(针对每个元素的个位进行排序处理)
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位的值
            int bucketIndex = arr[j] / 1 % 10;
            //放入到对应的桶中
            bucket[bucketIndex][bucketCountArr[bucketIndex]] = arr[j];
            bucketCountArr[bucketIndex]++;
        }
        //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
        int index = 0;
        //遍历每一桶，并将桶中是数据，放入到原数组
        for (int k = 0; k < bucketCountArr.length; k++) {
            //如果桶中，有数据，我们才放入到原数组
            if (bucketCountArr[k] != 0) {
                //循环该桶即第k个桶(即第k个一维数组), 放入
                for (int l = 0; l < bucketCountArr[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
            bucketCountArr[k] = 0;

        }
        System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));

        //第2轮(针对每个元素的个位进行排序处理)
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位的值
            int bucketIndex = arr[j] / 10 % 10;
            //放入到对应的桶中
            bucket[bucketIndex][bucketCountArr[bucketIndex]] = arr[j];
            bucketCountArr[bucketIndex]++;
        }
        //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
        index = 0;
        //遍历每一桶，并将桶中是数据，放入到原数组
        for (int k = 0; k < bucketCountArr.length; k++) {
            //如果桶中，有数据，我们才放入到原数组
            if (bucketCountArr[k] != 0) {
                //循环该桶即第k个桶(即第k个一维数组), 放入
                for (int l = 0; l < bucketCountArr[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
            bucketCountArr[k] = 0;

        }
        System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));

        //第3轮(针对每个元素的个位进行排序处理)
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位的值
            int bucketIndex = arr[j] / 100 % 10;
            //放入到对应的桶中
            bucket[bucketIndex][bucketCountArr[bucketIndex]] = arr[j];
            bucketCountArr[bucketIndex]++;
        }
        //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
        index = 0;
        //遍历每一桶，并将桶中是数据，放入到原数组
        for (int k = 0; k < bucketCountArr.length; k++) {
            //如果桶中，有数据，我们才放入到原数组
            if (bucketCountArr[k] != 0) {
                //循环该桶即第k个桶(即第k个一维数组), 放入
                for (int l = 0; l < bucketCountArr[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
            bucketCountArr[k] = 0;

        }
        System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr));


        return arr;
    }


    static int maxCount(int arr[]) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            int j = arr[i];
            String s = String.valueOf(j);
            int length = s.length();
            if (length > max) max = length;
        }
        return max;
    }



    /**
     * 基数排序（分位数排序） 支持负数
     * @param arr
     * @return
     */
    static int[] radixSortF(int arr[]) {
        long l = System.currentTimeMillis();
        //计算出最大的位数是几位数，就要几次大循环
        int count = maxCount(arr);
        /**
         * 定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
         * 1. 二维数组包含10个一维数组
         * 2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
         * 3. 明确，基数排序是使用空间换时间的经典算法
         */
        int[][] bucket = new int[19][arr.length];
        //记录每一个桶中存放的数据数量
        int[] bucketCountArr = new int[19];
        for (int i = 0; i < count; i++) {
            //遍历原始数组
            for (int j = 0; j < arr.length; j++) {
                //处理个位数，按照第一次进来,%取余
                int v = arr[j] / (int) (Math.pow(10, i)) % 10;
                //放进对应的桶里，且记录好在桶里的位置
                bucket[v+9][bucketCountArr[v+9]] = arr[j];
                //放了数字以后桶中的元素个数需要加一
                bucketCountArr[v+9]++;
            }

            //辅助变量，帮忙把桶中的元素全部复制到原始数组中
            int index = 0;
            //遍历桶数据量数组，不为0的就需要遍历其值，从桶中拿出对应的数放回原始数组
            for (int k = 0; k < bucketCountArr.length; k++) {
                if (bucketCountArr[k] != 0) {
                    for (int m = 0; m < bucketCountArr[k]; m++) {
                        //k，代表k号桶，m代表桶中的第m个元素
                        arr[index++] = bucket[k][m];
                    }
                    //记得把桶数量计数器清零
                    bucketCountArr[k] = 0;
                }
            }
            System.out.printf("第%d次排序结果" + Arrays.toString(arr), i + 1);
            System.out.println("");
        }
        System.out.println("耗时" + (System.currentTimeMillis() - l) + "ms");
        return arr;
    }
}
